package com.clps.algorithm.chapter04.展平多级双向链表;

import java.util.WeakHashMap;

/**
 * 在一个多级双向链表中节点除了有两个指针分别指向前后两个节点之外，还有一个指针指向它的子链表，并且子链表也是一个双向链表，它的节点也有指向子链表的指针。
 * 请将这样的多级双向链表展平成普通的双向链表，即所有节点都没有子链表。
 * 例如图4.14（a）是一个多级双向链表，它展平之后如图4.14（b）所示。
 * 展平多级双向链表。（a）一个多级双向链表。（b）展平之后的双向链表。
 */
public class demo01 {
    public static void main(String[] args) {

    }

    public Node flatten(Node head) {
        flattenGetTail(head);
        return head;
    }

    private Node flattenGetTail(Node head) {
        Node node = head;
        Node tail = null;
        while (node != null) {
            Node next = node.next;

            if (node.child != null) {
                Node child = node.child;
                Node childTail = flattenGetTail(node.child);

                node.child = null;
                node.next = child;
                child.prev = node;
                childTail.next = next;
                if(next!=null) {
                    next.prev = childTail;
                }
                tail = childTail;
            }else {
                tail = node;
            }
        }
        return tail;
    }

}
